Power Aware Real Time Scheduling in Constrained Devices

Real-time scheduling algorithms, such as Rate Monotonic and Earliest Deadline First, guarantee that calculations are performed within a pre-defined time. As many real-time systems operate on limited battery power, these algorithms have been enhanced with power-aware properties. In this thesis, 13 power-aware real-time scheduling algorithms for processor, device and system-level use are explored.

Oncolytic adenoviruses for treatment of ovarian cancer

Virotherapy, the use of oncolytic properties of viruses for eradication of tumor cells, is an attractive strategy for treating cancers resistant to traditional modalities. Adenoviruses can be genetically modified to selectively replicate in and destroy tumor cells through exploitation of molecular differences between normal and cancer cells. The lytic life cycle of adenoviruses results in oncolysis of infected cells and spreading of virus progeny to surrounding cells. In this study, we evaluated different strategies for improving safety and efficacy of oncolytic virotherapy against human ovarian adenocarcinoma. We examined the antitumor efficacy of Ad5/3-Δ24, a serotype 3 receptor-targeted pRb-p16 pathway-selective oncolytic adenovirus, in combination with conventional chemotherapeutic agents. We observed synergistic activity in ovarian cancer cells when Ad5/3-Δ24 was given with either gemcitabine or epirubicin, common second-line treatment options for ovarian cancer. Our results also indicate that gemcitabine reduces the initial rate of Ad5/3-Δ24 replication without affecting the total amount of virus produced. In an orthotopic murine model of peritoneally disseminated ovarian cancer, combining Ad5/3-Δ24 with either gemcitabine or epirubicin resulted in greater therapeutic benefit than either agent alone. Another useful approach for increasing the efficacy of oncolytic agents is to arm viruses with therapeutic transgenes such as genes encoding prodrug-converting enzymes. We constructed Ad5/3-Δ24-TK-GFP, an oncolytic adenovirus encoding the thymidine kinase (TK) green fluorescent protein (GFP) fusion protein. This novel virus replicated efficiently on ovarian cancer cells, which correlated with increased GFP expression. Delivery of prodrug ganciclovir (GCV) immediately after infection abrogated viral replication, which might have utility as a safety switch mechanism. Oncolytic potency in vitro was enhanced by GCV in one cell line, and the interaction was not dependent on scheduling of the treatments. However, in murine models of metastatic ovarian cancer, administration of GCV did not add therapeutic benefit to this highly potent oncolytic agent. Detection of tumor progression and virus replication with bioluminescence and fluorescence imaging provided insight into the in vivo kinetics of oncolysis in living mice. For optimizing protocols for upcoming clinical trials, we utilized orthotopic murine models of ovarian cancer to analyze the effect of dose and scheduling of intraperitoneally delivered Ad5/3-Δ24. Weekly administration of Ad5/3-Δ24 did not significantly enhance antitumor efficacy over a single treatment. Our results also demonstrate that even a single intraperitoneal injection of only 100 viral particles significantly increased the survival of mice compared with untreated animals. Improved knowledge of adenovirus biology has resulted in creation of more effective oncolytic agents. However, with more potent therapy regimens an increase in unwanted side-effects is also possible. Therefore, inhibiting viral replication when necessary would be beneficial. We evaluated the antiviral activity of chlorpromazine and apigenin on adenovirus replication and associated toxicity in fresh human liver samples, normal cells, and ovarian cancer cells. Further, human xenografts in mice were utilized to evaluate antitumor efficacy, viral replication, and liver toxicity. Our data suggest that these agents can reduce replication of adenoviruses, which could provide a safety switch in case of replication-associated side-effects. In conclusion, we demonstrate that Ad5/3-Δ24 is a useful oncolytic agent for treatment of ovarian cancer either alone or in combination with conventional chemotherapeutic drugs. Insertion of genes encoding prodrug-converting enzymes into the genome of Ad5/3-Δ24 might not lead to enhanced antitumor efficacy with this highly potent oncolytic virus. As a safety feature, viral activity can be inhibited with pharmacological substances. Clinical trials are however needed to confirm if these preclinical results can be translated into efficacy in humans. Promising safety data seen here, and in previous publications suggest that clinical evaluation of the agent is feasible.

Optimisation Problems in Wireless Sensor Networks : Local Algorithms and Local Graphs

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.

Optimisation problems in wireless sensor networks

This thesis studies optimisation problems related to modern large-scale distributed systems, such as wireless sensor networks and wireless ad-hoc networks. The concrete tasks that we use as motivating examples are the following: (i) maximising the lifetime of a battery-powered wireless sensor network, (ii) maximising the capacity of a wireless communication network, and (iii) minimising the number of sensors in a surveillance application. A sensor node consumes energy both when it is transmitting or forwarding data, and when it is performing measurements. Hence task (i), lifetime maximisation, can be approached from two different perspectives. First, we can seek for optimal data flows that make the most out of the energy resources available in the network; such optimisation problems are examples of so-called max-min linear programs. Second, we can conserve energy by putting redundant sensors into sleep mode; we arrive at the sleep scheduling problem, in which the objective is to find an optimal schedule that determines when each sensor node is asleep and when it is awake. In a wireless network simultaneous radio transmissions may interfere with each other. Task (ii), capacity maximisation, therefore gives rise to another scheduling problem, the activity scheduling problem, in which the objective is to find a minimum-length conflict-free schedule that satisfies the data transmission requirements of all wireless communication links. Task (iii), minimising the number of sensors, is related to the classical graph problem of finding a minimum dominating set. However, if we are not only interested in detecting an intruder but also locating the intruder, it is not sufficient to solve the dominating set problem; formulations such as minimum-size identifying codes and locating–dominating codes are more appropriate. This thesis presents approximation algorithms for each of these optimisation problems, i.e., for max-min linear programs, sleep scheduling, activity scheduling, identifying codes, and locating–dominating codes. Two complementary approaches are taken. The main focus is on local algorithms, which are constant-time distributed algorithms. The contributions include local approximation algorithms for max-min linear programs, sleep scheduling, and activity scheduling. In the case of max-min linear programs, tight upper and lower bounds are proved for the best possible approximation ratio that can be achieved by any local algorithm. The second approach is the study of centralised polynomial-time algorithms in local graphs – these are geometric graphs whose structure exhibits spatial locality. Among other contributions, it is shown that while identifying codes and locating–dominating codes are hard to approximate in general graphs, they admit a polynomial-time approximation scheme in local graphs.